package demo1;
import java.security.KeyStore;
import java.util.*;


/**
 * 给定一个单词列表 words 和一个整数 k ，返回前 k 个出现次数最多的单词。
 *
 * 返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率， 按字典顺序 排序。*/

/**
 * 思路一：
 *     使用HashMap计数，使用小根堆进行排序*/
class Solution {
    public List<String> topKFrequent(String[] words, int k) {
        //1. 遍历数组，计数
        HashMap<String, Integer> map = new HashMap<>();
        for (int i = 0; i < words.length; i++) {
            if (!map.containsKey(words[i])) {
                //不存在map中，put
                map.put(words[i], 1);
            } else {
                //存在则更新value值
                int count = map.get(words[i]) + 1;
                map.put(words[i], count);
            }
        }

        //2. 遍历map，将其中数据插入到小根堆进行排序
        //小根堆 最小值在根节点处，故可以比较最小元素 //大根堆 最大值在根结点处
        PriorityQueue<Map.Entry<String, Integer>> minHeap = new PriorityQueue<>(new Comparator<Map.Entry<String, Integer>>() {
            //Map.Entry 可看作是链表的Node
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                if(o1.getValue().compareTo(o2.getValue())==0) {
                    return o2.getKey().compareTo(o1.getKey());
                }
                return o1.getValue().compareTo(o2.getValue());
            }
        });

        //map可以使用Map.Entry 进行foreach遍历
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            //先入堆k个元素
            if (minHeap.size()<k) {
                minHeap.offer(entry);
            } else {
                Map.Entry<String,Integer> top = minHeap.peek();
                if(top.getValue()<entry.getValue()) {
                    minHeap.poll();
                    minHeap.offer(entry);
                } else if(top.getValue()==entry.getValue()) {
                    if(top.getKey().compareTo(entry.getKey())>0) {
                        minHeap.poll();
                        minHeap.offer(entry);
                    }
                }
            }
        }
        List<String> ret = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            Map.Entry<String, Integer> top = minHeap.poll();
            ret.add(top.getKey());
        }
        Collections.reverse(ret);
        return ret;
    }
}

/**
 * 思路二：
 *     先使用HashMap进行计数，使用大根堆进行排序，再插入k个值到返回容器中即可*/
class SolutionOther {
    public List<String> topKFrequent(String[] words, int k) {
        //1. 遍历数组，计数
        HashMap<String, Integer> map = new HashMap<>();
        for (int i = 0; i < words.length; i++) {
            if (!map.containsKey(words[i])) {
                //不存在map中，put
                map.put(words[i], 1);
            } else {
                //存在则更新value值
                int count = map.get(words[i]) + 1;
                map.put(words[i], count);
            }
        }

        //2. 遍历map，将所有数据插入到顺序表中
        List<Map.Entry<String,Integer>> list = new ArrayList<>();
        for(Map.Entry<String,Integer> entry : map.entrySet()) {
            list.add(entry);
        }

        Comparator<Map.Entry<String,Integer>> cmpToWords = new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                //字典序
                return o1.getKey().compareTo(o2.getKey());
            }
        };

        Comparator<Map.Entry<String,Integer>> cmpToCount = new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                //
                return o2.getValue().compareTo(o1.getValue());
            }
        };
        //先按照字典序进行排序
        insertSort(list,cmpToWords);
        insertSort(list,cmpToCount);
        List<String> ret = new ArrayList<>();
        for(int i = 0; i < k; i++) {
            ret.add(list.get(i).getKey());
        }
        return ret;
    }

    //均使用tmp作为o1 和每个值进行比较
    private void insertSort(List<Map.Entry<String,Integer>> list, Comparator<Map.Entry<String,Integer>> cmp) {
        for(int i = 1; i < list.size(); i++) {
            int j = i-1;
            Map.Entry<String,Integer> tmp = list.get(i);

            while(j>=0) {
                if(cmp.compare(tmp,list.get(j))<0) {
                    //将j+1 位置下标设置为j下标的值
                    list.set((j+1),list.get(j));
                    j--;
                } else {
                    break;
                }
            }
            list.set((j+1),tmp);
        }
    }
}